package leetcode

/*
 * @lc app=leetcode.cn id=1319 lang=golang
 *

 * [1319] 连通网络的操作次数
 */

// @lc code=start
func makeConnected(n int, connections [][]int) int {
	if len(connections) < n-1 {
		return -1
	}

	uf := newUnionFind(n)
	for _, c := range connections {
		uf.union(c[0], c[1])
	}
	return uf.setCount - 1
}

type unionFind struct {
	parent, size []int
	setCount     int // 当前连通分量数目
}

func newUnionFind(n int) *unionFind {
	parent := make([]int, n)
	size := make([]int, n)
	for i := range parent {
		parent[i] = i
		size[i] = 1
	}
	return &unionFind{parent, size, n}
}

func (uf *unionFind) find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *unionFind) union(x, y int) {
	fx, fy := uf.find(x), uf.find(y)
	if fx == fy {
		return
	}
	if uf.size[fx] < uf.size[fy] {
		fx, fy = fy, fx
	}
	uf.size[fx] += uf.size[fy]
	uf.parent[fy] = fx
	uf.setCount--
}

// @lc code=end
